/*
 * @lc app=leetcode.cn id=464 lang=cpp
 *
 * [464] 我能赢吗
 */

// @lc code=start
class Solution {
public:
    bool dfs(int maxChoosableInteger, int desiredTotal,
             unordered_map<int, bool> &m, int mask) {
        if (m.find(mask) != m.end()) return m[mask];
        for (int i = 1; i <= maxChoosableInteger; i++) {
            if (mask & (1 << i)) continue;
            if (i >= desiredTotal) return true;
            if (!dfs(maxChoosableInteger, desiredTotal - i, m,
                     mask | (1 << i))) {
                m[mask] = true;
                return true;
            }
        }
        m[mask] = false;
        return false;
    }
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
            return false;

        unordered_map<int, bool> m;
        int mask = 0;

        return dfs(maxChoosableInteger, desiredTotal, m, mask);
    }
};
// @lc code=end
